// #include <stdio.h>
// #include <stdlib.h>
// #include <Windows.h>
// #include <stdbool.h>
// #include <time.h>
//
// typedef char ElemType;
// // 节点结构
// typedef struct Node {
//     ElemType data;
//     struct Node* next;
// } Node;
//
// // 链表结构
// typedef struct LinkedList {
//     Node* head;  // 头结点
// } LinkedList;
//
// //栈结构(装入链表节点)
// typedef struct SNode {
//     Node* data;
//     struct SNode* next;
// }SNode;
//
// //栈顶指针
// typedef struct  Stack {
//     SNode* top;
// }Stack;
//
// //初始化栈
// void InitStack(Stack* S) {
//     S->top=NULL;
// }
//
// //判断栈空
// bool IsStackNull(Stack* S) {
//    return S->top==NULL;
// }
//
// //入栈
// void PushStack(Stack* S,Node* node) {
//     if(S==NULL||node==NULL) {
//         return;
//     }
//     SNode* newNode=(SNode*)malloc(sizeof(SNode));
//     if(newNode==NULL) {
//         printf("内存分配失败\n");
//         return;
//     }
//     newNode->data=node;
//     newNode->next=S->top;
//     S->top=newNode;
// }
//
// //出栈
// Node* PopStack(Stack* S) {
//     if(S->top==NULL) {
//         return NULL;
//     }
//     SNode* tmp=S->top;
//     S->top=S->top->next;
//     return tmp->data;
// }
//
// // 创建链表并初始化
// LinkedList* create_list() {
//     LinkedList* list = (LinkedList*)malloc(sizeof(LinkedList));
//     if (list == NULL) {
//         printf("内存分配失败\n");
//         exit(1);
//     }
//     list->head = (Node*)malloc(sizeof(Node)); // 创建头结点
//     if (list->head == NULL) {
//         printf("内存分配失败\n");
//         free(list);
//         exit(1);
//     }
//     list->head->next = NULL;  // 初始化头结点的下一个指针
//     return list;
// }
//
// // 判断链表是否为空
// int is_empty(LinkedList* list) {
//     return list->head->next == NULL;
// }
//
// // 尾插法插入
// void insert_at_tail(LinkedList* list, ElemType data) {
//     Node* new_node = (Node*)malloc(sizeof(Node));
//     if (new_node == NULL) {
//         printf("内存分配失败\n");
//         exit(1);
//     }
//     new_node->data = data;
//     new_node->next = NULL;
//
//     Node* current = list->head;
//     while (current->next != NULL) {
//         current = current->next;
//     }
//     current->next = new_node;
// }
//
// // 显示链表内容
// void display(LinkedList* list) {
//     Node* current = list->head->next;
//     printf("链表内容: ");
//     while (current != NULL) {
//         printf("%c ", current->data);
//         current = current->next;
//     }
//     printf("\n");
// }
//
// // 释放链表内存
// void free_list(LinkedList* list) {
//     Node* current = list->head;
//     while (current != NULL) {
//         Node* next_node = current->next;
//         free(current);
//         current = next_node;
//     }
//     free(list);
// }
//
// //判断字符对称，思路：快慢指针找到中点，后半链表节点依次入栈，再出栈比较
// bool IsCenterDuiChen(LinkedList* L) {
//     if(L==NULL) {
//         //链表没申请成功内存退出程序
//         exit(1);
//     }
//     //临时栈
//     Stack S;
//     InitStack(&S);
//     //快慢指针找到中点
//     Node* fast=L->head->next;
//     Node* slow=L->head->next;
//     Node* prev=NULL;//记录slow前一个节点
//     while (fast!=NULL&&fast->next!=NULL) {
//         prev=slow;
//         slow=slow->next;
//         fast=fast->next->next;
//     }
//     //后半部分入栈
//     Node* p=NULL;//后半部分链表的遍历指针
//     bool isoddlength=(fast!=NULL);
//     if(isoddlength) {
//         //链表长度为奇数
//         p=slow->next;
//     }else {
//         //链表长度为偶数
//         p=slow;
//     }
//     while (p!=NULL) {
//         PushStack(&S,p);
//         p=p->next;
//     }
//     //比较前半部分和栈的元素
//     Node* t=L->head->next;
//     while (!IsStackNull(&S)) {
//         Node* tmp=PopStack(&S);
//         if(t->data!=tmp->data) {
//             return false;
//         }
//         t=t->next;
//     }
//     return true;
// }
//
// int main() {
//     SetConsoleOutputCP(CP_UTF8);
//     LinkedList* L=create_list();
//     insert_at_tail(L,'x');
//     insert_at_tail(L,'y');
//     insert_at_tail(L,'y');
//     insert_at_tail(L,'x');
//
//     LinkedList* L2=create_list();
//     insert_at_tail(L2,'x');
//     insert_at_tail(L2,'y');
//     insert_at_tail(L2,'z');
//     insert_at_tail(L2,'y');
//     insert_at_tail(L2,'y');
//
//     bool result=IsCenterDuiChen(L);
//     if(result) {
//         printf("是对称\n");
//     }else {
//         printf("不是对称\n");
//     }
//
//     bool result2=IsCenterDuiChen(L2);
//     if(result2) {
//         printf("是对称\n");
//     }else {
//         printf("不是对称\n");
//     }
//
//     return 0;
// }